package cn.mengfly.algorithm.collection.queue;

import java.util.Iterator;

/**
 * @author wangp
 */
public class LinkedQueue<T> implements Queue<T> {

    private int size;

    /**
     * linked head
     */
    private Node<T> head;
    /**
     * linked tail
     */
    private Node<T> tail;


    @Override
    public void enqueue(T t) {
        Node<T> oldTail = tail;

        tail = new Node<>();
        tail.item = t;

        if (isEmpty()) {
            head = tail;
        } else {
            oldTail.next = tail;
        }

        size++;
    }

    @Override
    public T dequeue() {

        if (isEmpty()) {
            return null;
        }

        Node<T> dequeue = head;

        if (head == tail) {
            tail = null;
        }
        head = head.next;

        size--;
        return dequeue.item;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void clear() {
        for (Node<T> x = head; head.next != null; ) {
            Node<T> next = x.next;
            x.next = null;
            x.item = null;
            x = next;
        }
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            LinkedQueue.Node<T> curNode = head;

            @Override
            public boolean hasNext() {
                return curNode == null;
            }

            @Override
            public T next() {
                T res = curNode.item;
                curNode = curNode.next;
                return res;
            }
        };
    }

    private static class Node<T> {
        T item;
        Node<T> next;
    }
}
